﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0010_FirstUniqChar
    {
        // 字符串中的第一个唯一字符

        // 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

        // 提示：你可以假定该字符串只包含小写字母。

        public void Test()
        {
            var s = "aabb";
            Console.WriteLine(FirstUniqChar1(s));
            Console.Read();
        }

        //框架api O(n)
        public int FirstUniqChar(string s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                if (s.IndexOf(s[i]) == s.LastIndexOf(s[i]))
                    return i;
            }
            return -1;
        }

        //循环 O(n^2)
        public int FirstUniqChar1(string s)
        {
            for (int i = 0; i < s.Length; i++)
            {
                var flag = false;
                for (int j = 0; j < s.Length; j++)
                {
                    if (i == j)
                        continue;

                    if (s[i] == s[j])
                    {
                        flag = true;
                        break;
                    }
                }
                if (!flag)
                    return i;
            }
            return -1;
        }

        //两次遍历O(n)
        public int FirstUniqChar2(string s)
        {
            var count = new int[26];
            char[] chars = s.ToCharArray();
            //先统计每个字符出现的次数
            for (int i = 0; i < s.Length; i++)
                count[chars[i] - 'a']++;
            //然后在遍历字符串s中的字符，如果出现次数是1就直接返回
            for (int i = 0; i < s.Length; i++)
                if (count[chars[i] - 'a'] == 1)
                    return i;
            return -1;
        }

        //hash（同上）
        //略
    }
}
